#include<unordered_map>
using std::unordered_map;


struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};



class Solution {

public:
    int pathSum(TreeNode* root, int targetSum) {
        int rootSelect = rootSum(root, targetSum, true);
        int rootNoSelect = rootSum(root, targetSum, false);
        return rootNoSelect + rootSelect;
    }

    int rootSum(TreeNode* root, int target, bool select) {
        if (!root) return 0;
        if (select) {
            int target2 = target - root->val;
            return 1*(target2 == 0) + rootSum(root->left, target2, select) + rootSum(root->right, target2, select);
        }
        else {
            return rootSum(root->left, target, true) + rootSum(root->left, target, false) +
                    rootSum(root->right, target, true) + rootSum(root->right, target, false);
        }
    }
    

    
};